package shapes.shapes2D.distribution.poissondisk 
{
	import flash.geom.Point;
	import flash.geom.Rectangle;
	import shapes.shapes2D.Dot;
	import utils.GeomUtils;
	
	/**
	 * 
	 * http://www.devmag.org.za/articles/55-POISSON-DISK-SAMPLING/#top2
	 * 
	 * @author Nicolas Barradeau
	 * http://en.nicoptere.net
	 */
	public class PoissonDisk
	{
		static private var cellSize:Number;
		//static private var min_dist:Number;
		static private var min_dist_square:Number;
		static private var grid:Vector.<Point>;
		static private var processList:Vector.<Point>;
		static private var samplePoints:Vector.<Point>;
		static private var width:int;
		static private var height:int;
		
		
		static private var totalCell:int;
		static private var cellWidth:int;
		static private var cellHeight:int;
		
		public function PoissonDisk() 
		{
			
		}
		static public function generate_poisson( rect:Rectangle, min_dist:Number = 10, new_points_count:int = 50 ):Vector.<Point>
		{
			//Create the grid
			cellSize = min_dist / Math.SQRT2;
			
			//PoissonDisk.min_dist = min_dist;
			min_dist_square = min_dist * min_dist;
			
			width = rect.width;
			height = rect.height;
			
			cellWidth = int( width / cellSize );
			cellHeight = int( height / cellSize );
			totalCell = cellWidth * cellHeight;
			
			grid = new Vector.<Point>();
			grid.length = totalCell;
			grid.fixed = true;
			
			
			//RandomQueue works like a queue, except that it
			//pops a random element from the queue instead of
			//the element at the head of the queue
			processList = new Vector.<Point>();
			samplePoints = new Vector.<Point>();

			//generate the first point randomly
			//and updates 

			var firstPoint:Point = new Point( Math.random() * width, Math.random() * height );
			var point:Point;
			var newPoint:Point;
			
			//update containers
			processList.push(firstPoint); 
			samplePoints.push(firstPoint);
			
			grid[ imageToGrid( firstPoint ) ] = firstPoint;
			
			var i:int;
			//generate other points from points in queue.
			while ( processList.length > 0 )
			{
				point = processList.pop();
				
				for (i = 0; i < new_points_count; i++)
				{
					
					newPoint = generateRandomPointAround( point, min_dist );
					
					//check that the point is in the image region
					//and no points exists in the point's neighbourhood
					if ( 	rect.contains( newPoint.x, newPoint.y )
					&&		!inNeighbourhood( newPoint, min_dist ) )
					{
						//update containers
						samplePoints.push(newPoint);
						processList.push(newPoint);
						grid[ imageToGrid(newPoint)] = newPoint;
					}
				}
			}
			return samplePoints;
		}
		
		static private function generateRandomPointAround( point:Point, mindist:Number ):Point
		{
			
			//random radius between mindist and 2 * mindist
			var radius:Number = mindist * ( Math.random() + 1);
			
			//random angle
			var angle:Number = 2 * Math.PI * Math.random();
			
			//the new point is generated around the point (x, y)
			return new Point( 	point.x + radius * Math.cos(angle),
								point.y + radius * Math.sin(angle) 	);
		
		}
		
		static private function inNeighbourhood( point:Point, mindist:Number ):Boolean
		{
			if ( grid.length <= 0 ) return false;
			
			var dx:Number, dy:Number;
			for each( var p:Point in grid )
			{
				
				if ( null != p )
				{
					dx = point.x - p.x;
					dy = point.y - p.y;
					if ( ( dx * dx + dy * dy ) < min_dist_square ) return true;
				}
			}
			return false
			
			//get the neighbourhood if the point in the grid
			//cellsAroundPoint = squareAroundPoint( imageToGrid( point ) );
			//
			//var p:Point = grid[ imageToGrid( point ) ];
			//var center:int =  imageToGrid( point );
			//var i0:int, i1:int;
			//
			//i0 = center - ( 2 * cellWidth ) - 1;
			//i1 = center + ( 2 * cellWidth ) + 1;
			//
			//if ( i0 < 0 ) i0 = 0;
			//if ( i1 >= totalCell ) i1 = totalCell - 1;
			//
			//var tl:Point = 
			//
			//
			//for every cell in cellsAroundPoint
				//if (cell != null)
				//if distance(cell, point) < mindist
				//return true
		}
		
		static private function squareAroundPoint( id:int ):Vector.<Point>
		{
			var cells:Vector.<Point> = new Vector.<Point>();
			return cells
		}
		
		static private function imageToGrid( point:Point ):int
		{
			return int( int( point.x / width ) % cellSize ) + int( int( point.y / height )  / cellSize);
		}
		
		
	}

}
	